Class TreeBag<T>

An implementation of Red-Black trees as an indexed, sorted collection with bag semantics, cf. CLRS. (TreeBag<T> for an implementation with set semantics).
The comparer (sorting order) may be either natural, because the item type is comparable (generic: or non-generic: System.IComparable) or it can be external and supplied by the user in the constructor.
Each distinct item is only kept in one place in the tree - together with the number of times it is a member of the bag. Thus, if two items that are equal according

Implements

IEnumerable<T>, System.Collections.IEnumerable, System.IFormattable, System.ICloneable, System.IDisposable, ICollection<T>, ICollectionValue<T>, IDirectedCollectionValue<T>, IDirectedEnumerable<T>, IExtensible<T>, IIndexed<T>, IIndexedSorted<T>, IPersistentSorted<T>, ISequenced<T>, IShowable, ISorted<T>

Bases

object, EnumerableBase<T>, CollectionValueBase<T>, CollectionBase<T>, DirectedCollectionBase<T>, SequencedBase<T>

Field overview

isReadOnly, Inherited from CollectionBase<T> ,
itemequalityComparer, Inherited from CollectionBase<T> ,
size, Inherited from CollectionBase<T> ,
stamp, Inherited from CollectionBase<T>

Event overview

CollectionChanged, Inherited from CollectionValueBase<T> ,
CollectionCleared, Inherited from CollectionValueBase<T> ,
ItemInserted, Inherited from CollectionValueBase<T> ,
ItemRemovedAt, Inherited from CollectionValueBase<T> ,
ItemsAdded, Inherited from CollectionValueBase<T> ,
ItemsRemoved, Inherited from CollectionValueBase<T>

Property overview

ActiveEvents, Inherited from CollectionValueBase<T> ,
AllowsDuplicates ,
Comparer ,
ContainsSpeed ,
Count, Inherited from CollectionBase<T> ,
CountSpeed, Inherited from CollectionBase<T> ,
Direction, Inherited from SequencedBase<T> ,
DuplicatesByCounting ,
EqualityComparer, Inherited from CollectionBase<T> ,
IndexingSpeed ,
IsEmpty, Inherited from CollectionBase<T> ,
IsReadOnly, Inherited from CollectionBase<T> ,
this[int i] ,
this[int start, int end] ,
ListenableEvents ,
maxsnapid ,
SyncRoot, Inherited from CollectionBase<T>

Constructor overview

TreeBag<T>() ,
TreeBag<T>(System.Collections.Generic.IComparer<T> comparer) ,
TreeBag<T>(System.Collections.Generic.IComparer<T> comparer, System.Collections.Generic.IEqualityComparer<T> equalityComparer)

Method overview

Add(T item) ,
AddAll<U>(IEnumerable<U> items) ,
AddSorted<U>(IEnumerable<U> items) ,
All(Fun<T,bool> predicate), Inherited from CollectionValueBase<T> ,
Apply(Act<T> action), Inherited from CollectionValueBase<T> ,
Backwards() ,
Check(string name) ,
Check() ,
checkRange(int start, int count), Inherited from CollectionBase<T> ,
Choose() ,
Clear() ,
Clone() ,
Contains(T item) ,
ContainsAll<U>(IEnumerable<U> items) ,
ContainsCount(T item) ,
CopyTo(T[] array, int index), Inherited from CollectionValueBase<T> ,
CountFrom(T bot) ,
CountFromTo(T bot, T top) ,
CountTo(T top) ,
Cut(System.IComparable<T> c, out T low, out bool lowIsValid, out T high, out bool highIsValid) ,
DeleteMax() ,
DeleteMin() ,
Dispose() ,
dump() ,
dump(string msg) ,
Equals(object obj), Inherited from object ,
Exists(Fun<T,bool> predicate), Inherited from CollectionValueBase<T> ,
Filter(Fun<T,bool> predicate), Inherited from CollectionValueBase<T> ,
Finalize(), Inherited from object ,
Find(ref T item) ,
Find(Fun<T,bool> predicate, out T item), Inherited from CollectionValueBase<T> ,
FindAll(Fun<T,bool> filter) ,
FindIndex(Fun<T,bool> predicate), Inherited from SequencedBase<T> ,
FindLast(Fun<T,bool> predicate, out T item), Inherited from DirectedCollectionBase<T> ,
FindLastIndex(Fun<T,bool> predicate), Inherited from SequencedBase<T> ,
FindMax() ,
FindMin() ,
FindOrAdd(ref T item) ,
GetEnumerator() ,
GetHashCode(), Inherited from object ,
GetSequencedHashCode(), Inherited from SequencedBase<T> ,
GetType(), Inherited from object ,
GetUnsequencedHashCode(), Inherited from CollectionBase<T> ,
IndexOf(T item) ,
ItemMultiplicities() ,
LastIndexOf(T item) ,
Map<V>(Fun<T,V> mapper, System.Collections.Generic.IComparer<V> c) ,
MemberwiseClone(), Inherited from object ,
modifycheck(int thestamp), Inherited from CollectionBase<T> ,
Predecessor(T item) ,
raiseCollectionChanged(), Inherited from CollectionValueBase<T> ,
raiseCollectionCleared(bool full, int count), Inherited from CollectionValueBase<T> ,
raiseCollectionCleared(bool full, int count, System.Nullable<int> offset), Inherited from CollectionValueBase<T> ,
raiseForAdd(T item), Inherited from CollectionValueBase<T> ,
raiseForInsert(int i, T item), Inherited from CollectionValueBase<T> ,
raiseForRemove(T item), Inherited from CollectionValueBase<T> ,
raiseForRemove(T item, int count), Inherited from CollectionValueBase<T> ,
raiseForRemoveAll(ICollectionValue<T> wasRemoved), Inherited from CollectionValueBase<T> ,
raiseForRemoveAt(int index, T item), Inherited from CollectionValueBase<T> ,
raiseForSetThis(int index, T value, T item), Inherited from CollectionValueBase<T> ,
raiseForUpdate(T newitem, T olditem), Inherited from CollectionValueBase<T> ,
raiseForUpdate(T newitem, T olditem, int count), Inherited from CollectionValueBase<T> ,
raiseItemInserted(T item, int index), Inherited from CollectionValueBase<T> ,
raiseItemRemovedAt(T item, int index), Inherited from CollectionValueBase<T> ,
raiseItemsAdded(T item, int count), Inherited from CollectionValueBase<T> ,
raiseItemsRemoved(T item, int count), Inherited from CollectionValueBase<T> ,
RangeAll() ,
RangeFrom(T bot) ,
RangeFromTo(T bot, T top) ,
RangeTo(T top) ,
Remove(T item) ,
Remove(T item, out T removeditem) ,
RemoveAll<U>(IEnumerable<U> items) ,
RemoveAllCopies(T item) ,
RemoveAt(int i) ,
RemoveInterval(int start, int count) ,
RemoveRangeFrom(T low) ,
RemoveRangeFromTo(T low, T hi) ,
RemoveRangeTo(T hi) ,
RetainAll<U>(IEnumerable<U> items) ,
SequencedEquals(ISequenced<T> otherCollection), Inherited from SequencedBase<T> ,
Show(System.Text.StringBuilder stringbuilder, ref int rest, System.IFormatProvider formatProvider), Inherited from CollectionValueBase<T> ,
Snapshot() ,
Successor(T item) ,
ToArray(), Inherited from CollectionValueBase<T> ,
ToString(string format, System.IFormatProvider formatProvider), Inherited from CollectionValueBase<T> ,
ToString(), Inherited from CollectionValueBase<T> ,
UniqueItems() ,
UnsequencedEquals(ICollection<T> otherCollection), Inherited from CollectionBase<T> ,
Update(T item) ,
Update(T item, out T olditem) ,
updatecheck(), Inherited from CollectionBase<T> ,
UpdateOrAdd(T item) ,
UpdateOrAdd(T item, out T olditem) ,
WeakPredecessor(T item) ,
WeakSuccessor(T item)

Property details

F bool AllowsDuplicatesAccess: Read-Only

Value:True since this collection has bag semantics.

F System.Collections.Generic.IComparer<T> ComparerAccess: Read-Only

Value:The comparer

The comparer object supplied at creation time for this collection
F Speed ContainsSpeedAccess: Read-Only

Value:Speed.Log

The value is symbolic indicating the type of asymptotic complexity in terms of the size of this collection (worst-case or amortized as relevant).
bool DuplicatesByCountingAccess: Read-Only

Value:True if only one representative of a group of equal items is kept in the collection together with the total count.

By convention this is true for any collection with set semantics.
Speed IndexingSpeedAccess: Read-Only

Value:

F T this[int i]Access: Read-Only

Value:The i'th item of this list.

/ThrowsSystem.IndexOutOfRangeException if i is negative or >= the size of the collection.
Parameters:
i:the index to lookup
F IDirectedCollectionValue<T> this[int start, int end]Access: Read-Only

Value:The directed collection of items in a specific index interval.

/ThrowsSystem.IndexOutOfRangeException.
Parameters:
start:The low index of the interval (inclusive).
end:The high index of the interval (exclusive).
EventTypeEnum ListenableEventsAccess: Read-Only

Value:

int maxsnapidAccess: Read-Only

Constructor details

TreeBag<T>() Create a red-black tree collection with natural comparer and item equalityComparer. We assume that if T is comparable, its default equalityComparer will be compatible with the comparer.
Throws
NotComparableExceptionIf T is not comparable.
TreeBag<T>(System.Collections.Generic.IComparer<T> comparer) Create a red-black tree collection with an external comparer.

The itemequalityComparer will be a compatible ComparerZeroHashCodeEqualityComparer<T> since the default equalityComparer for T (EqualityComparer<T>.Default) is unlikely to be compatible with the external comparer. This makes the tree inadequate for use as item in a collection of unsequenced or sequenced sets or bags (ICollection<T> and ISequenced<T>)

Parameters:
comparer:The external comparer
TreeBag<T>(System.Collections.Generic.IComparer<T> comparer, System.Collections.Generic.IEqualityComparer<T> equalityComparer) Create a red-black tree collection with an external comparer and an external item equalityComparer, assumed consistent.
Parameters:
comparer:The external comparer
equalityComparer:The external item equalityComparer

Method details

F bool Add(T item) Add an item to this collection if possible. If this collection has set semantics, the item will be added if not already in the collection. If bag semantics, the item will always be added.
Returns:True if item was added.
Parameters:
item:The item to add.
F void AddAll<U>(IEnumerable<U> items) Add the elements from another collection with a more specialized item type to this collection. If this collection has set semantics, only items not already in the collection will be added.
Type parameters:
UThe type of items to add
Constraints:
U : T
Parameters:
items:The items to add
F void AddSorted<U>(IEnumerable<U> items) Add all the items from another collection with an enumeration order that is increasing in the items.

The idea is that the implementation may use a faster algorithm to merge the two collections.

/ThrowsSystem.ArgumentException if the enumerated items turns out not to be in increasing order.
Type parameters:
U
Constraints:
U : T
Parameters:
items:The collection to add.
IDirectedCollectionValue<T> Backwards() Create a collection containing the same items as this collection, but whose enumerator will enumerate the items backwards. The new collection will become invalid if the original is modified. Method typicaly used as in foreach (T x in coll.Backwards()) {...}
Returns:The backwards collection.
N bool Check(string name) Checks red-black invariant. Dumps tree to console if bad
Returns:false if invariant violation
Parameters:
name:Title of dump
F bool Check() Checks red-black invariant. Dumps tree to console if bad
Returns:false if invariant violation
T Choose()
Throws
NoSuchItemExceptionIf tree is empty
Returns:
F void Clear() Remove all items from this collection.
object Clone() Make a shallow copy of this TreeBag.
Returns:
F bool Contains(T item) Check if this collection contains (an item equivalent to according to the itemequalityComparer) a particular value.
Returns:True if the items is in this collection.
Parameters:
item:The value to check for.
F bool ContainsAll<U>(IEnumerable<U> items) Check if this collection contains all the values in another collection. If this collection has bag semantics (AllowsDuplicates==true) the check is made with respect to multiplicities, else multiplicities are not taken into account.
Type parameters:
U
Constraints:
U : T
Returns:True if all values in itemsis in this collection.
Parameters:
items:The
F int ContainsCount(T item) Count the number of items of the collection equal to a particular value. Returns 0 if and only if the value is not in the collection.
Returns:The number of copies found.
Parameters:
item:The value to count.
F int CountFrom(T bot) Determine the number of items at or above a supplied threshold.
Returns:The number of matcing items.
Parameters:
bot:The lower bound (inclusive)
F int CountFromTo(T bot, T top) Determine the number of items between two supplied thresholds.
Returns:The number of matcing items.
Parameters:
bot:The lower bound (inclusive)
top:The upper bound (exclusive)
F int CountTo(T top) Determine the number of items below a supplied threshold.
Returns:The number of matcing items.
Parameters:
top:The upper bound (exclusive)
F bool Cut(System.IComparable<T> c, out T low, out bool lowIsValid, out T high, out bool highIsValid) Perform a search in the sorted collection for the ranges in which a non-increasing (i.e. weakly decrerasing) function from the item type to int is negative, zero respectively positive. If the supplied cut function is not non-increasing, the result of this call is undefined.
Returns:
Parameters:
c:The cut function T to int, given as an IComparable<T> object, where the cut function is the c.CompareTo(T that) method.
low:Returns the largest item in the collection, where the cut function is positive (if any).
lowIsValid:True if the cut function is positive somewhere on this collection.
high:Returns the least item in the collection, where the cut function is negative (if any).
highIsValid:True if the cut function is negative somewhere on this collection.
F T DeleteMax() Remove the largest item from this priority queue.
Returns:The removed item.
F T DeleteMin() Remove the least item from this priority queue.
Returns:The removed item.
F void Dispose() If this tree is a snapshot, remove registration in base tree
N void dump() Print the tree structure to the console stdout.
N void dump(string msg) Print the tree structure to the console stdout.
F bool Find(ref T item) Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, return in the ref argument (a binary copy of) the actual value found.
Returns:True if the items is in this collection.
Parameters:
item:The value to look for.
F IIndexedSorted<T> FindAll(Fun<T,bool> filter) Create a new indexed sorted collection consisting of the items of this indexed sorted collection satisfying a certain predicate.
Returns:The new indexed sorted collection.
Parameters:
filter:The filter delegate defining the predicate.
F T FindMax() Find the current largest item of this priority queue.
Returns:The largest item.
F T FindMin() Find the current least item of this priority queue.
Returns:The least item.
F bool FindOrAdd(ref T item) Find or add the item to the tree. If the tree does not contain an item equivalent to this item add it, else return the exisiting one in the ref argument.
Returns:True if item was found
Parameters:
item:
System.Collections.Generic.IEnumerator<T> GetEnumerator() Create an enumerator for this tree
Returns:The enumerator
F int IndexOf(T item) Searches for an item in this indexed collection going forwards from the start.
Returns:Index of first occurrence from start of the item if found, else the two-complement (always negative) of the index at which the item would be put if it was added.
Parameters:
item:Item to search for.
ICollectionValue<KeyValuePair<T,int>> ItemMultiplicities()
Returns:
F int LastIndexOf(T item) Searches for an item in the tree going backwords from the end.
Returns:Index of last occurrence from the end of item if found, else the two-complement (always negative) of the index at which the item would be put if it was added.
Parameters:
item:Item to search for.
F IIndexedSorted<V> Map<V>(Fun<T,V> mapper, System.Collections.Generic.IComparer<V> c) Create a new indexed sorted collection consisting of the results of mapping all items of this list. /ThrowsSystem.ArgumentException if the map is not increasing over the items of this collection (with respect to the two given comparison relations).
Returns:The new sorted collection.
Parameters:
mapper:The delegate definging the map.
c:The comparion relation to use for the result.
F T Predecessor(T item) Find the strict predecessor in the sorted collection of a particular value, i.e. the largest item in the collection less than the supplied value.
Throws
NoSuchItemException if no such element exists (the supplied value is less than or equal to the minimum of this collection.)
Returns:The predecessor.
Parameters:
item:The item to find the predecessor for.
F IDirectedCollectionValue<T> RangeAll() Create a directed collection with the same items as this collection.
Returns:The result directed collection.
F IDirectedCollectionValue<T> RangeFrom(T bot) Query this sorted collection for items greater than or equal to a supplied value.
Returns:The result directed collection.
Parameters:
bot:The lower bound (inclusive).
F IDirectedCollectionValue<T> RangeFromTo(T bot, T top) Query this sorted collection for items between two supplied values.
Returns:The result directed collection.
Parameters:
bot:The lower bound (inclusive).
top:The upper bound (exclusive).
F IDirectedCollectionValue<T> RangeTo(T top) Query this sorted collection for items less than a supplied value.
Returns:The result directed collection.
Parameters:
top:The upper bound (exclusive).
F bool Remove(T item) Remove a particular item from this collection. If the collection has bag semantics only one copy equivalent to the supplied item is removed.
Returns:True if the item was found (and removed).
Parameters:
item:The value to remove.
F bool Remove(T item, out T removeditem) Remove a particular item from this collection if found. If the collection has bag semantics only one copy equivalent to the supplied item is removed, which one is implementation dependent. If an item was removed, report a binary copy of the actual item removed in the argument.
Returns:True if the item was found (and removed).
Parameters:
item:The value to remove.
removeditem:The removed value.
F void RemoveAll<U>(IEnumerable<U> items) Remove all items in another collection from this one. If this collection has bag semantics, take multiplicities into account.
Type parameters:
U
Constraints:
U : T
Parameters:
items:The items to remove.
F void RemoveAllCopies(T item) Remove all items equivalent to a given value.
Parameters:
item:The value to remove.
F T RemoveAt(int i) Remove the item at a specific position of the list. /ThrowsSystem.IndexOutOfRangeException if i is negative or >= the size of the collection.
Returns:The removed item.
Parameters:
i:The index of the item to remove.
F void RemoveInterval(int start, int count) Remove all items in an index interval. /ThrowsSystem.IndexOutOfRangeException???.
Parameters:
start:The index of the first item to remove.
count:The number of items to remove.
F void RemoveRangeFrom(T low) Remove all items of this collection above or at a supplied threshold.
Parameters:
low:The lower threshold (inclusive).
F void RemoveRangeFromTo(T low, T hi) Remove all items of this collection between two supplied thresholds.
Parameters:
low:The lower threshold (inclusive).
hi:The upper threshold (exclusive).
F void RemoveRangeTo(T hi) Remove all items of this collection below a supplied threshold.
Parameters:
hi:The upper threshold (exclusive).
F void RetainAll<U>(IEnumerable<U> items) Remove all items not in some other collection from this one. If this collection has bag semantics, take multiplicities into account.
Type parameters:
U
Constraints:
U : T
Parameters:
items:The items to retain.
F ISorted<T> Snapshot() Make a (read-only) snapshot of this collection.
Returns:The snapshot.
F T Successor(T item) Find the strict successor in the sorted collection of a particular value, i.e. the least item in the collection greater than the supplied value.
Throws
NoSuchItemException if no such element exists (the supplied value is greater than or equal to the maximum of this collection.)
Returns:The successor.
Parameters:
item:The item to find the successor for.
ICollectionValue<T> UniqueItems()
Returns:
F bool Update(T item) Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, update the item in the collection to with a binary copy of the supplied value. If the collection has bag semantics, this updates all equivalent copies in the collection.
Returns:True if the item was found and hence updated.
Parameters:
item:Value to update.
F bool Update(T item, out T olditem) Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, update the item in the collection with a binary copy of the supplied value. If the collection has bag semantics, this updates all equivalent copies in the collection.
Returns:
Parameters:
item:
olditem:
F bool UpdateOrAdd(T item) Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, update the item in the collection with a binary copy of the supplied value; else add the value to the collection. NOTE: the bag implementation is currently wrong! ?????
Returns:True if the item was found and updated (hence not added).
Parameters:
item:Value to add or update.
F bool UpdateOrAdd(T item, out T olditem)
Returns:
Parameters:
item:
olditem:
F T WeakPredecessor(T item) Find the weak predecessor in the sorted collection of a particular value, i.e. the largest item in the collection less than or equal to the supplied value.
Throws
NoSuchItemException if no such element exists (the supplied value is less than the minimum of this collection.)
Returns:The weak predecessor.
Parameters:
item:The item to find the weak predecessor for.
F T WeakSuccessor(T item) Find the weak successor in the sorted collection of a particular value, i.e. the least item in the collection greater than or equal to the supplied value. /ThrowsC5.NoSuchItemException if no such element exists (the supplied value is greater than the maximum of this collection.)
Returns:The weak successor.
Parameters:
item:The item to find the weak successor for.